1. Field of the Invention
The present invention relates to a device and a method for outputting stochastic processes, and a data recording medium. More particularly, the present invention relates to a device and a method for outputting stochastic processes, and a data recording medium which realize high speed simulation by utilizing a chaotic map based on an addition formula of a tangent function, especially for simulating Lxc3xa9vy""s stable processes which represent fluctuation of stock prices or exchanges, or transmission times in the World Wide Web (WWW) traffic.
2. Description of the Related Art
Not only physical phenomena, chemical phenomena, biological phenomena, and the like, various activities in the human society such as merchandizing, money transfer, and value shifts have been simulated with utilizing models of stochastic processes for analyzing them to find out the best solution.
In the conventional simulations, it has been assumed that shift stationary increment during a predetermined period in the stochastic process obey an explicit density function for distribution such as Gaussian distribution. In other words, random values in the stochastic process have been obtained by utilizing the von Neumann inverse function method to obtain random variables in accordance with the density function after generating uniform random variables.
It has been known that transmission times in the WWW traffic, stock price fluctuation, price fluctuation in the foreign exchange market, or the like during a predetermined period (for example, several seconds or several minutes) shifts in accordance with the Lxc3xa9vy distribution (stable distribution) (R. N. Mantegna and H. E.
Stanley, Nature, vol. 376, pp. 46-49, 1995). The Lxc3xa9vy distribution is a distribution having parameters of indexes xcex1 and xcex2 (equation 1). By the Lxc3xa9vy distribution, it is impossible to obtain an analytic density function unless the indexes xcex1 and xcex2 show specific values. On the contrary, a Normal (Gaussian) distribution is able to show an analytic density function.
P(x; xcex1, xcex2)={fraction (1/2xcfx80)}∫xe2x88x92∞∞exp(izx)"psgr"(z)dzxe2x80x83xe2x80x83EQUATION 1
where
"psgr"(z)=exp{xe2x88x92ixcex3zxe2x88x92xcex7|z|xcex1[1+ixcex2sgn(z)xcfx89(z, xcex1)]}
0 less than xcex1xe2x89xa62
xe2x88x921xe2x89xa6xcex2xe2x89xa61
xcex3xe2x89xa70
xcfx89(z, xcex1)=tan(xcfx80xcex1/2) for xcex1xe2x89xa01
xcfx89(z, xcex1)=(2/xcfx80) log |z | for xcex1=1
In case of obtaining the Lxc3xa9vy""s stable processes with utilizing the von Neumann inverse function method, Fourier integration must be carried out once as shown by equation 1 to obtain a density function, further, time-integration of random variables obtained by the density function is required in order to obtain Lxc3xa9vy""s stable processes. A result after these computationally heavy steps is, however, an approximation.
The Cauthy distribution is a distribution by which its density function is obtained explicitly. The Cauthy distribution corresponds to the Lxc3xa9vy distribution at xcex1=1 and xcex2=0. It has been observed that the Lxc3xa9vy distribution but not the Cauthy distribution appears in the empirical data of distribution of transmission times in WWW traffic traffic, stock price fluctuation, price fluctuation in the foreign exchange market, or the like.
Accordingly, integrating process must be carried out many times in the conventional technique, because it requires time-integration of the stationary increments obtained by the von Neumann inverse function method after generating uniform random variables and Fourier integration. As a result, it requires very long process time for calculation. Moreover, the result of the simulation is not reliable due to the truncation of the limits of integration.
Demands for efficient simulations such as technical simulation for developing improved communication protocol, industrial simulation for evaluating financial risks corresponding to fluctuation of stock prices or exchanges have been developing. In other words, great demand for simulating the Lxc3xa9vy""s stable processes has been raised in the industry field.
The present invention have made in consideration of the above. It is an object of the present invention to provide a device and a method for outputting stochastic processes, and a data recording medium. More particularly, it is an object of the present invention to provide a device and a method for outputting stochastic processes, and a data recording medium which realize high speed simulation by utilizing a chaotic map based on an addition formula of a tangent function, especially for simulating Lxc3xa9vy""s stable processes which represents fluctuation of stock prices or exchanges, or transmission times in the WWW traffic.
The present invention for accomplishing the above objects will now be disclosed in accordance with its principle.
FIG. 1 is a block diagram schematically showing a device for outputting stochastic process according to the present invention. As shown in FIG. 1, an output device 101 for outputting stochastic process according to the present invention comprises a plurality of random variable output units 102, a normalizing unit 103, and a result output unit 104.
Each of the random variable output units 102 outputs random variable sequence 105 which obeys an analytical density function of limit distribution. The normalizing unit 103 normalizes the sum of the random variables in the same row over the plurality of sequences 105 output by the plurality of random variable output units 102. The result output unit 104 time-integrates normalized values 106 sequentially supplied by the normalizing unit 103, and sequentially outputs the time-integrated value as result values in the stochastic process.
The result values 107 sequentially output by the result output unit 104 represent the stochastic process such as Lxc3xa9vy""s stable processes.
Calculations carried out by the random variable output units 102 are not related to each other. Therefore, the random variable output units 102 can perform concurrent calculation or parallel calculation independently. An SIMD (Single Instruction Multi Data) parallel computer is available for simulating stochastic process in a case where the plurality of the random variable output units 102 do the same calculations but handling different data. The SIMD parallel computer realizes high speed simulation.
The density function of limit distribution in the sequence output by each random variable output unit 102 may be a function xcfx80(xc2x7) having the characteristics shown in equation 2.
xcfx81(x)≅cxe2x88x92|x|xe2x88x92(1+xcex1) for xxe2x86x92xe2x88x92∞
xcfx81(x)≅c+|x|xe2x88x92(1+xcex1) for xxe2x86x92+∞xe2x80x83xe2x80x83EQUATION 2
where 0 less than xcex1xe2x89xa62
In a case where the number of the random variable output units 102 is N and the i-th (1xe2x89xa6ixe2x89xa6N) random variable output unit 102 outputs a sequence (x(i, 0), x(i, 1), x(i, 2), . . . ) of random variables, the normalizing unit 103 outputs a sequence xe2x80x9c(v(0), v(1), v(2), . . . )xe2x80x9d of normalized values obtained by equation 3, and the result output unit 104 outputs a sequence xe2x80x9c(L(0), L(1), L(2), . . . )xe2x80x9d of result values obtained by equation 4.                                                                         v                ⁡                                  (                  t                  )                                            =                                                                                          ∑                                              i                        =                        1                                            N                                        ⁢                                          xe2x80x83                                        ⁢                                          x                      ⁡                                              (                                                  i                          ,                          t                                                )                                                                              -                  A                                B                                                                        xe2x80x83                                                          xe2x80x83                                                                                          A                =                0                            ,                                                          B              =                              N                                  1                  /                  α                                                                                                        for                ⁢                                  xe2x80x83                                ⁢                0                             less than               α               less than               1                                                                                          A                =                0                            ,                                                          B              =              N                                                                                            for                  ⁢                                      xe2x80x83                                    ⁢                  α                                =                1                            ,                                                x                  _                                =                0                                                                                                        A                =                                                      N                    2                                    ⁢                                                            sin                      ⁢                                              x                        N                                                              _                                                              ,                                                          B              =              N                                                                                            for                  ⁢                                      xe2x80x83                                    ⁢                  α                                =                1                            ,                              x                ≠                0                                                                                                        A                =                                  N                  ⁢                                      x                    _                                                              ,                                                          B              =                              N                                  1                  /                  α                                                                                                        for                ⁢                                  xe2x80x83                                ⁢                1                             less than               α               less than               2                                                          EQUATION  3            
where {overscore (x)} is the expectation value of the random variable output x by the random variable output units                               L          ⁡                      (            t            )                          =                              ∑                          j              =              0                        t                    ⁢                      xe2x80x83                    ⁢                      v            ⁡                          (              j              )                                                          EQUATION  4            
It has been proved that the normalized value sequence xe2x80x9cv(0), v(1), v(2), . . . xe2x80x9d shows random variables in accordance with the Lxc3xa9vy distribution (stable distribution) when N is fully large. (B. V. Gnedenko and A. N. Kolmogorov, Limit Distributions for Sums of Independent Random Variables, Addison Wesley, Reading, Mass., 1954)
The sequence of the random variables xe2x80x9cx(i, 0), x(i, 1), x(i, 2), . . . xe2x80x9d output by the random variable output units 102 may be obtained by a recurrence formula x(i, t+1)=f(x(i, t)) which utilizing a function f(xc2x7) obtained by equation 5.                               f          ⁡                      (            x            )                          =                  {                                                                                                                1                                              δ                        1                                                              ⁢                                          g                      ⁡                                              (                                                                              δ                            1                                                    ⁢                          x                                                )                                                              ⁢                                          xe2x80x83                                        ⁢                    for                    ⁢                                          xe2x80x83                                        ⁢                    x                                    ∈                                      X                    ++                                                                                                                                                                  1                                              δ                        2                                                              ⁢                                          g                      ⁡                                              (                                                                              δ                            1                                                    ⁢                          x                                                )                                                              ⁢                                          xe2x80x83                                        ⁢                    for                    ⁢                                          xe2x80x83                                        ⁢                    x                                    ∈                                      X                                          +                      -                                                                                                                                                                                      1                                              δ                        1                                                              ⁢                                          g                      ⁡                                              (                                                                              δ                            2                                                    ⁢                          x                                                )                                                              ⁢                                          xe2x80x83                                        ⁢                    for                    ⁢                                          xe2x80x83                                        ⁢                    x                                    ∈                                      X                                          -                      +                                                                                                                                                                                      1                                              δ                        2                                                              ⁢                                          g                      ⁡                                              (                                                                              δ                            2                                                    ⁢                          x                                                )                                                              ⁢                                          xe2x80x83                                        ⁢                    for                    ⁢                                          xe2x80x83                                        ⁢                    x                                    ∈                                      X                    --                                                                                                          EQUATION  5            
where xcex41 greater than 0, xcex42 greater than 0
g(x) is a function defined by any one of the followings:
a step function sgn(x) satisfying the followings;
sgn(x)=1 for x greater than 0
sgn(x)=xe2x88x921 for x less than 0
any one of the following xcfx861 to xcfx868; and
xcfx861(xcex8)=xe2x88x92sgn(tan xcex8)/|tan xcex8|l/xcex1
xcfx862(xcex8)=xe2x88x92sgn(tan xcex8)xc3x97|tan xcex8|l/xcex1
xcfx863(xcex8)=xe2x88x92sgn(cos xcex8)/|tan xcex8|l/xcex1
xcfx864(xcex8)=xe2x88x92sgn(cos xcex8)xc3x97|tan xcex8|l/xcex1
xcfx865(xcex8)=sgn(cos xcex8)/|tan xcex8|l/xcex1
xcfx866(xcex8)=sgn(cos xcex8)xc3x97|tan xcex8|l/xcex1
xcfx867(xcex8)=sgn(sin xcex8)/|tan xcex8|l/xcex1
xcfx868(xcex8)=sgn(sin xcex8)xc3x97|tan xcex8|l/xcex1
xcfx86i(lxcex8)=g(xcfx86i(lxcex8)) for 1xe2x89xa6ixe2x89xa68
where l is a natural number equal to or greater than 2
X++ represents a legion of x where g(x)xe2x89xa70 and xxe2x89xa70
X+xe2x88x92 represents a region of x where g(x) less than 0 and xxe2x89xa70
Xxe2x88x92+ represents a region of x where g(x)xe2x89xa70 and x less than 0
Xxe2x88x92xe2x88x92 represents a region of x where g(x) less than 0 and x less than 0
FIG. 2 is a block diagram schematically showing the structure of the random variable output unit 102. Like or same reference numerals used in FIG. 1 are also used in FIG. 2 to denote corresponding or identical components.
The random variable output unit 102 comprises a storage unit 202, an output unit 203, a calculator 203, and an update unit 205.
The storage unit 202 stores a random variable 105 to be output next. The output unit 203 outputs the random variable 105 in the storage unit 202. The calculator 204 calculates a predetermined function for which the random variable 105 in the storage unit 202 is substituted to obtain a result 207. The update unit 205 supplies the result 207 to the storage unit 202 for storing.
FIG. 3 is a block diagram schematically showing the structure of the result output unit 104 in the device 100 for outputting stochastic process according to the present invention. Like or same reference numerals used in FIG. 1 are also used in FIG. 3 to denote corresponding or identical components.
The result output unit 104 comprises a storage unit 302 for storing integrated values, an output unit 303 for outputting integrated values, a sum calculator 304, and an update unit 305 for updating integrated values.
The integrated value storage unit 302 stores integrated values, and the output unit 303 outputs the values in the integrated value storage unit 302 as the results 107 of the stochastic process. The sum calculator 304 calculates a sum 306 of the value 106 output by the normalizing unit 103 and the value 107 in the storage unit 302. The update unit 305 supplies the sum 306 to the storage unit 302 for storing.
Here, the results 107 sequentially output by the normalizing unit 103 represent the Lxc3xa9vy""s stable processes. That is, increment of the results 107 represent the value 106 output by the normalizing unit 103, thus, the value 106 is output in accordance with the Lxc3xa9vy stable distribution.
A method of outputting stochastic process according to the present invention may include the steps of outputting random variables, outputting normalized values, and outputting results.
In the random variable output step, a plurality of sequences of random variables represented by a function for obtaining an analytical density function of limit distribution are output. In the normalized value outputting step, the sum of the random variables in the same row over the sequences output by the random variable outputting step is normalized. In the result outputting step, values sequentially output by the normalized value outputting step are time-integrated, and the integrated values are sequentially output as a result in the stochastic process.
Each of density functions of limit distribution for the random variable sequences output by the random variable outputting step of the method according to the present invention may be a function xcfx81(xc2x7) having the characteristics shown by equation 6.
xcfx81(x)≅cxe2x88x92|x|xe2x88x92(1+xcex1) for xxe2x86x92xe2x88x92∞
xcfx81(x)≅c+|x|xe2x88x92(1+xcex1) for xxe2x86x92+∞xe2x80x83xe2x80x83EQUATION 6
where 0 less than xcex1xe2x89xa62
In a case where the number of the random variable sequences output by the random variable outputting step is N and the i-th (1xe2x89xa6ixe2x89xa6N) sequence is (x(i, 0), x(i, 1), x(i, 2), . . . ), the normalized value outputting step outputs a sequence xe2x80x9c(v(0), v(1), v(2), . . . )xe2x80x9d of normalized values obtained by equation 7, and the result outputting step outputs a sequence xe2x80x9c(L(0), L(1), L(2), . . . )xe2x80x9d of result values obtained by equation 8.                                                                         v                ⁡                                  (                  t                  )                                            =                                                                                          ∑                                              i                        =                        1                                            N                                        ⁢                                          xe2x80x83                                        ⁢                                          x                      ⁡                                              (                                                  i                          ,                          t                                                )                                                                              -                  A                                B                                                                        xe2x80x83                                                          xe2x80x83                                                                                          A                =                0                            ,                                                          B              =                              N                                  1                  /                  α                                                                                                        for                ⁢                                  xe2x80x83                                ⁢                0                             less than               α               less than               1                                                                                          A                =                0                            ,                                                          B              =              N                                                                                            for                  ⁢                                      xe2x80x83                                    ⁢                  α                                =                1                            ,                                                x                  _                                =                0                                                                                                        A                =                                                      N                    2                                    ⁢                                                            sin                      ⁢                                              x                        N                                                              _                                                              ,                                                          B              =              N                                                                                            for                  ⁢                                      xe2x80x83                                    ⁢                  α                                =                1                            ,                              x                ≠                0                                                                                                        A                =                                  N                  ⁢                                      x                    _                                                              ,                                                          B              =                              N                                  1                  /                  α                                                                                                        for                ⁢                                  xe2x80x83                                ⁢                1                             less than               α               less than               2                                                          EQUATION  7            
where {overscore (x)} is the expectation value of the random variable output x by the random variable output units                               L          ⁡                      (            t            )                          =                              ∑                          j              =              0                        t                    ⁢                      xe2x80x83                    ⁢                      v            ⁡                          (              j              )                                                          EQUATION  8            
The sequence of the random variables x(i, 0), x(i, 1), x(i, 2), . . . output by the random variable outputting step may be obtained by a recurrence formula x(i, t+1) =f(x(i, t)) which utilizing a function f(xc2x7) obtained by equation 9.                               f          ⁡                      (            x            )                          =                  {                                                                                                                1                                              δ                        1                                                              ⁢                                          g                      ⁡                                              (                                                                              δ                            1                                                    ⁢                          x                                                )                                                              ⁢                                          xe2x80x83                                        ⁢                    for                    ⁢                                          xe2x80x83                                        ⁢                    x                                    ∈                                      X                    ++                                                                                                                                                                  1                                              δ                        2                                                              ⁢                                          g                      ⁡                                              (                                                                              δ                            1                                                    ⁢                          x                                                )                                                              ⁢                                          xe2x80x83                                        ⁢                    for                    ⁢                                          xe2x80x83                                        ⁢                    x                                    ∈                                      X                                          +                      -                                                                                                                                                                                      1                                              δ                        1                                                              ⁢                                          g                      ⁡                                              (                                                                              δ                            2                                                    ⁢                          x                                                )                                                              ⁢                                          xe2x80x83                                        ⁢                    for                    ⁢                                          xe2x80x83                                        ⁢                    x                                    ∈                                      X                                          -                      +                                                                                                                                                                                      1                                              δ                        2                                                              ⁢                                          g                      ⁡                                              (                                                                              δ                            2                                                    ⁢                          x                                                )                                                              ⁢                                          xe2x80x83                                        ⁢                    for                    ⁢                                          xe2x80x83                                        ⁢                    x                                    ∈                                      X                    --                                                                                                          EQUATION  9            
where xcex41 greater than 0, xcex42 greater than 0
g(x) is a function defined by any one of the followings:
a step function sgn(x) satisfying the followings;
sgn(x)=1 for x greater than 0
sgn(x)=xe2x88x921 for x less than 0
any one of the following xcfx861 to xcfx868; and
xcfx861(xcex8)=xe2x88x92sgn(tan xcex8)/|tan xcex8|l/xcex1
xcfx862(xcex8)=xe2x88x92sgn(tan xcex8)xc3x97|tan xcex8|l/xcex1
xcfx863(xcex8)=xe2x88x92sgn(cos xcex8)/|tan xcex8|l/xcex1
xcfx864(xcex8)=xe2x88x92sgn(cos xcex8)xc3x97|tan xcex8|l/xcex1
xcfx865(xcex8)=sgn(cos xcex8)/|tan xcex8|l/xcex1
xcfx866(xcex8)=sgn(cos xcex8)xc3x97|tan xcex8|l/xcex1
xcfx867(xcex8)=sgn(sin xcex8)/|tan xcex8|l/xcex1
xcfx868(xcex8)=sgn(sin xcex8)xc3x97|tan xcex8|l/xcex1
xcfx86i(lxcex8)=g(xcfx86i(lxcex8)) for 1xe2x89xa6ixe2x89xa68
where l is a natural number equal to or greater than 2
X++ represents a legion of x where g(x)xe2x89xa70 and xxe2x89xa70
X+xe2x88x92 represents a region of x where g(x) less than 0 and xxe2x89xa70
Xxe2x88x92+ represents a region of x where g(x)xe2x89xa70 and x less than 0
Xxe2x88x92xe2x88x92 represents a region of x where g(x) less than 0 and x less than 0
The random variable outputting step of the method according to the present invention may include the steps of outputting, calculating, and updating.
In the outputting step, values stored in a plurality of storage units each storing a next random variable to be output are output. In the calculating step, a predetermined function for which the random variable in the storage unit is substituted is calculated. In the updating step, the results of the calculating step are supplied to the storage units for storing.
The result outputting step of the method according to the present invention may comprise the steps of outputting integrated values, calculating sum, and updating the integrated values.
In the integrated value outputting step, integrated values stored in storage are output as results in the stochastic process. In the sum calculation step, the value output by the normalizing step and the integrated value stored in the storage are added to each other. In the integrated value updating step, the sum calculated by the sum calculation step is supplied to the storage for storing.
Programs which realize the device and method for outputting stochastic process according to the present invention may be stored in a data recording medium such as a compact disc, a floppy disk, a hard disk, a magneto-optical disk, a digital versatile disc, a magnetic tape, and a semiconductor memory device.
The above described device and method for outputting stochastic process will be realized by executing the programs stored in a data recording medium according to the present invention by a data processor such as a general purpose computer and a parallel computer having a storage device, a calculator, an output device, and the like.
It is able to distribute and merchandize the data recording medium storing the programs according to the present invention as an independent product separated from the data processor.